package com.hyb.algorithm.data.struct.list;

/**
 * @Author: huyanbing
 * @Date: 2021/9/5 3:56 下午
 */
public class ReverseBetween {

    public static void main(String[] args) {

        int[] nums = new int[]{1, 2, 3, 4, 5};

        int len = nums.length;

        ListNode head = new ListNode(1);
        ListNode temp = head;
        for (int i = 1; i < len; i++) {
            ListNode listNode = new ListNode(nums[i]);

            temp.next = listNode;
            temp = listNode;
        }
        ReverseBetween exe = new ReverseBetween();

        ListNode res = exe.reverseBetween(head, 2, 4);

        System.out.println(res);
    }

    private ListNode successor = null;

    /**
     * m  从1 开始计数
     *
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        //m==1 的时候 相当于 reverseN 反转以 head 为起点的 n 个节点，返回新的头结点
        if (m == 1) {
            return reverseN(head, n);
        }

        // 前进到反转的起点触发 base case
        head.next= reverseBetween(head.next, m - 1, n - 1);
        return head;
    }


    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }

        ListNode last = reverseN(head.next, n - 1);


        head.next.next = head;
        head.next = successor;

        return last;

    }
}
